#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *removeNthFromEnd(ListNode *head, int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!head)
        return NULL;

    // move n-1 forward
    ListNode *curNode = head;
    for(int i=0; i<n-1; ++i){
        curNode = curNode->next;
        if(!curNode)
            break;
    }
    if(!curNode)
        return head;
    // now curNode points to n-1 Node
    ListNode *pDummy = new ListNode(0);
    pDummy->next = head;
    ListNode *pParent = pDummy;
    while(curNode->next){
        curNode = curNode->next;
        pParent = pParent->next;
    }
    // curNode points to the last one
    ListNode *pDelete = pParent->next;
    pParent->next = pDelete->next;
    delete pDelete;
    ListNode *res = pDummy->next;
    delete pDummy;
    return res;
}


int main(){
    return 0;
}